package priorityqueue;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

//oj题,给出一个数组,找出这个数组中的前k小的元素,以任意顺序返回这k个数即可
public class HeapProblem {

    //粗暴解法,创建一个小根堆,然后将数组中的元素添加进去,每次都返回根节点,但是这种解法的空间复杂度就很大
    //需要创建一个长度为arr.length的小堆的队列
//    public static int[] smallestK(int []arr,int k){
//
//        if(arr == null || k > arr.length){
//            return null;
//        }
//
//        PriorityQueue<Integer> queue = new PriorityQueue<>();
//        for(int i = 0;i < arr.length;i++){
//            queue.add(arr[i]);
//        }
//        int [] result = new int [k];
//        for(int i = 0;i < k;i++){
//            result[i] = queue.poll();
//        }
//        return result;
//    }

    //NB解法
    //改成创建长度为k的大堆序列,找出前k个最小的元素,思路如下
    //1,创建长度为k的大堆
    //2,遍历数组,把前k个元素插入到堆中
    //3,从k+1个元素开始遍历,拿着当前元素和堆顶元素来比较--
    //此处的堆顶就是前k个元素中最大的,也就是最不喜欢的,后面的比较元素如果比堆顶的元素小,就把堆顶元素顶掉
    //如果比堆顶的元素大,那就不需要动了

        public static int[] smallestK(int []arr,int k){
            if(arr == null){
                return null;
            }
            if(k == 0){
                int []result = new int[0];
                return result;
            }
        PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        for(int i = 0;i < k;i++){
            queue.add(arr[i]);
        }
        for(int i = k;i < arr.length;i++){
            if(arr[i] >= queue.peek()){
                continue;
            }else{
                queue.poll();
                queue.offer(arr[i]);
            }
        }
        int [] result = new int [k];
        for(int i = 0;i < k;i++){
            result[i] = queue.poll();
        }
        return result;
    }

    public static void main(String[] args) {
        int[] arr = {2,32,35,5,3,6,6,7,9};
        int [] result = smallestK(arr,4);
        System.out.println(Arrays.toString(result));
    }


}
